package com.hanxiaozhang.no10leetcode;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈寻找两个正序数组的中位数，要求算法的时间复杂度应该为 O(log (m+n)) 〉
 * <p>
 * 示例 1：
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2
 * 解释：合并数组 = [1,2,3]，中位数 2
 * <p>
 * 示例 2：
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.5
 * 解释：合并数组 = [1,2,3,4]，中位数 (2 + 3) / 2 = 2.5
 * <p>
 * 思路：
 * 1. 归并比较，将两个数组合并成一个新数组。 -> 重点如何使用循环：while (p1 < nums1.length && p2 < nums2.length)
 *   - nums1的数分别与nums2的数比较，然后插入新数组。
 *   - 上述步骤结束后，可能存在一个数组中的数，没有插入到新数组，将其插入
 * 2. 新数组二分查找。
 *
 * @author hanxinghua
 * @create 2023/12/21
 * @since 1.0.0
 */
public class No4FindMedianSortedArrays {


    public static void main(String[] args) {

        int[] nums1 = {1, 3};
        int[] nums2 = {2};

        System.out.println(mergeMethod(nums1, nums2));
    }


    /**
     * 归并比较
     *
     * @param nums1
     * @param nums2
     * @return
     */
    private static double mergeMethod(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length + nums2.length];
        int p1 = 0, p2 = 0, index = 0;

        while (p1 < nums1.length && p2 < nums2.length) {
            if (nums1[p1] <= nums2[p2]) {
                result[index++] = nums1[p1++];
            } else {
                result[index++] = nums2[p2++];
            }
        }
        while (p1 < nums1.length) {
            result[index++] = nums1[p1++];
        }
        while (p2 < nums2.length) {
            result[index++] = nums2[p2++];
        }
        System.out.println(Arrays.toString(result));

        int mid = result.length / 2;
        if (result.length % 2 == 0) {
            return result[mid];
        } else {
            return (result[mid] + result[mid + 1]) / 2;
        }
    }

    /**
     * 先pass
     *
     * @param nums1
     * @param nums2
     * @return
     */
    private static double dichotomicMethod(int[] nums1, int[] nums2) {
        return 0D;
    }
}
